#include<vector>
#include<iostream>
#include<string>
using namespace std;
bool check_col[10], check_row[10];
bool digit1[20], digit2[20];
vector<string> path;
vector<vector<string>> ret;
int n;
void dfs(int row)
{
    if (row == n)
    {
        ret.push_back(path);
        return;
    }
    for (int col =0 ; col < n; col++)
    {
        if (!check_row[row] && !check_col[col] && !digit1[col - row + n] && !digit2[col + row])
        {
            path[row][col] = 'Q';
            check_row[row] = check_col[col] = digit1[row - col + n] = digit2[col + row] = true;
            dfs(row + 1);
            path[row][col] = '.';
            check_row[row] = check_col[col] = digit1[row - col + n] = digit2[col + row] = false;
        }
    }
}
vector<vector<string>> solveNQueens(int _n) {
    n = _n;
    path.resize(n);
    for (int i = 0; i < n; i++) path[i].append(n, '.');
    dfs(0);
    return ret;

}

//int main() 
//{
//    ret =  solveNQueens(4);
//  //  cout << ret;
//    return 0;
//}